class Solution {
    public int fib(int n) {
        int MOD = 1000000007;
        if(n < 2){
            return n;
        }
        int q = 0;
        int q2 = 1;
        int num = 0;
        for(int i = 0; i < n; i++){
            q = q2;
            q2 = num;
            num = (q + q2) % MOD;
        }
        return num;
    }
}